package com.cat.dataStructure02;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

/**
 * @author 曲大人的喵
 * @description https://leetcode.cn/problems/sort-the-matrix-diagonally/
 * @create 2025/10/22 18:09
 * @since JDK17
 */

public class Solution44 {
    public int[][] diagonalSort(int[][] mat) {
        int n = mat.length, m = mat[0].length;
        List<Integer> list = new ArrayList<>();
        int x = n - 1, y = 0;
        for (int i = 0; i < m + n - 1; i++) {
            list.clear();
            int nx = x, ny = y;
            while (nx < n && ny < m) {
                list.add(mat[nx++][ny++]);
            }
            Collections.sort(list, (a, b) -> a - b);
            int j = 0;
            nx = x;
            ny = y;
            for(int num : list) {
                mat[nx++][ny++] = num;
            }
            if (x != 0) {
                x--;
            } else {
                y++;
            }
        }

        return mat;
    }
}
